#include <iostream>
#include <assert.h>
#include <string>
#include <vector>

using namespace std;

template<class K> struct BSTreeNode
{
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _data;

    BSTreeNode(const K& data)
        :_left(nullptr)
        , _right(nullptr)
        , _data(data)
    {}
};

template<class K> class BSTree
{
    typedef BSTreeNode<K> Node;
public:
    BSTree() {}
    BSTree(const K* a, size_t n)
    {
        for (size_t i = 0; i < n; i++)
            insert(a[i]);
    }
    BSTree(const BSTree<K>& tree) { _root = _Copy(tree._root); }

    BSTree<K>& operator=(BSTree<K> tree)
    {
        swap(_root, tree._root);
        return *this;
    }

    bool insert(const K& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            return true;
        }

        Node* cur = _root;
        Node* parent = nullptr;

        while (cur)
        {
            if (cur->_data > data)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_data < data)
            {
                parent = cur;
                cur = cur->_right;
            }
            else return false;
        }

        cur = new Node(data);
        if (parent->_data < data)
            parent->_right = cur;
        else
            parent->_left = cur;

        return true;
    }

    bool erase(const K& data)
    {
        if (!(find(data)))
            return false;

        Node* cur = _root;
        Node* parent = nullptr;

        while (cur)
        {
            if (cur->_data < data)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_data > data)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                if (cur->_left == nullptr)
                {
                    if (parent == nullptr)
                    {
                        _root = cur->_right;
                    }
                    else
                    {
                        if (parent->_left == cur)
                            parent->_left = cur->_right;
                        else
                            parent->_right = cur->_right;
                    }
                    delete cur;
                }
                else if (cur->_right == nullptr)
                {
                    if (parent == nullptr)
                    {
                        _root = cur->_left;
                    }
                    else
                    {
                        if (parent->_right == cur)
                            parent->_right = cur->_left;
                        else
                            parent->_left = cur->_right;
                    }
                    delete cur;
                }
                else
                {
                    Node* rightmin = cur->_right, * prightmin = cur;
                    while (rightmin->_left) { prightmin = rightmin; rightmin = rightmin->_left; }

                    swap(cur->_data, rightmin->_data);
                    if (prightmin->_right == rightmin)
                        prightmin->_right = rightmin->_right;
                    else
                        prightmin->_left = rightmin->_right;
                    delete rightmin;
                }

                return true;
            }
        }

        return false;
    }

    Node* find(const K& data)
    {
        if (_root == nullptr)
            return nullptr;

        Node* cur = _root;
        while (cur)
        {
            if (cur->_data < data)
                cur = cur->_right;
            else if (cur->_data > data)
                cur = cur->_left;
            else
                return cur;
        }

        return nullptr;
    }

    bool empty() const { return _root == nullptr; }

    void InOrder() { _InOrder(_root); cout << endl; }
    ~BSTree() { _Destroy(_root); }

    bool insertR(const K& data) { return _insertR(_root, data); }
    bool eraseR(const K& data) { return _eraseR(_root, data); }
    bool findR(const K& data) { return _findR(_root, data); }
    //Node* findR(const K& data) { return _findR(_root, data); }

private:

    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_data << ' ';
        _InOrder(root->_right);
    }

    void _Destroy(Node* root)
    {
        if (root == nullptr)
            return;

        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
        root = nullptr;
    }

    bool _insertR(Node*& root, const K& data)
    {
        if (root == nullptr)
        {
            root = new Node(data);
            return true;
        }

        if (root->_data < data)
            return _insertR(root->_right, data);
        else if (root->_data > data)
            return _insertR(root->_left, data);
        else return false;
    }

    bool _findR(Node* root, const K& data)
    {
        if (root == nullptr)
            return false;

        if (root->_data < data)
            return _findR(root->_right, data);
        else if (root->_data > data)
            return _findR(root->_left, data);
        else return true;
    }

    //Node* _findR(Node* root, const K& data)
    //{
    //    if (root == nullptr)
    //        return nullptr;

    //    if (root->_data < data)
    //        return _findR(root->_right, data);
    //    else if (root->_data > data)
    //        return _findR(root->_left, data);
    //    else return root;
    //}
    
    bool _eraseR(Node*& root, const K& data)
    {
        if (root == nullptr)
            return false;

        if (root->_data < data)
            return _eraseR(root->_right, data);
        else if (root->_data > data)
            return _eraseR(root->_left, data);
        else
        {
            Node* del = root;

            if (root->_left == nullptr)
                root = root->_right;
            else if (root->_right == nullptr)
                root = root->_left;
            else
            {
                Node* min = root->_right;
                while (min->_left) { min = min->_left; }

                swap(root->_data, min->_data);
                return _eraseR(root->_right, data);
            }

            delete del;
            return true;
        }
    }

    Node* _Copy(Node* root)
    {
        if (root == nullptr)
            return nullptr;

        Node* copyNode = new Node(root->_data);
        copyNode->_left = _Copy(root->_left);
        copyNode->_right = _Copy(root->_right);

        return copyNode;
    }

private:
    Node* _root = nullptr;
};

